/*
 * =====================================================================================
 *
 *       Filename:  kmin.c
 *
 *    Description:  find the k least number
 *
 *        Version:  1.0
 *        Created:  2012年03月13日 16时18分47秒
 *       Revision:  none
 *       Compiler:  gcc
 *
 *         Author:  Regan (), lcqhigh@gmail.com
 *        Company:  
 *
 * =====================================================================================
 */

#include	<stdio.h>
#include	"utility.h"
#include	<algorithm>
#include	<assert.h>

int expectedk;

//站在巨人们的肩膀上的缘故
int partion(int arr[], int n)
{
    int off = 0;
    int cmpvalue = arr[0];
    for (int i = 1; i < n; ++i)
    {
        if (arr[i] < cmpvalue)
        {
            ++off;
            std::swap(arr[i], arr[off]);            
        }
    }
    //don't ignore
    std::swap(arr[0], arr[off]);
    return off+1;
}

int partion2(int *x, int n)
{
    int pivot = 0;
    int mid = abs(rand()) % n;
    if (n > 2) {
        --n;
        if (mid < 1 || mid > n-1)
            mid = 1;
        if (x[0] > x[mid]) std::swap(x[0], x[mid]);
        if (x[0] > x[n])   std::swap(x[0], x[n]);
        if (x[mid] > x[n]) std::swap(x[mid], x[n]);

        std::swap(x[mid], x[n-1]);
        int l = 0, h = n - 1;
        for (;;) {
            while (x[++l] < x[n-1]);
            while (x[--h] > x[n-1]);
            if (l >= h)
                break;
            std::swap(x[l], x[h]);
        }
        std::swap(x[l], x[n-1]);
        pivot = l;
    } else if (n == 2 && x[0] > x[1]) {
        std::swap(x[0], x[1]);
        pivot = 1;
    }
    return pivot+1;
}



void findKmin(int arr[], int n)
{
    if (n == 0)
        return;
    if (n == expectedk)
    {
        return;
    }

    int sp = partion(arr, n);
    if (sp <= expectedk)
    {
        expectedk -= sp;      
        if (expectedk > 0)
            findKmin(arr+sp, n-sp);
    }
    else
    {
        //must minus one
        findKmin(arr, sp-1);
    }
    return;
}



void test()
{
    int arr[11600];
    int res[11600];
    int arrlen = sizeof(arr)/sizeof(arr[0]) - 1;
    int times = 5000;
    int savedk = 0;

    srand(time_t(NULL));

    while (times--)
    {
        expectedk = rand() % 306 + 1;
        savedk = expectedk;
        genRandInt(arr, arrlen);

        //printf ( "the %d min value is\n", savedk);
        findKmin(arr, arrlen);
        
        //printIntarr(arr, savedk);
        //printf ( "********************************\n" );

        std::copy(arr, arr+savedk, res); 
        std::sort(arr, arr+arrlen);
        //printIntarr(arr, savedk);
        for (int idx = 0; idx < savedk; ++idx) 
            assert(std::find(res, res+savedk, arr[idx]) != (res+savedk));
        
        //printf ( "==================================\n" );
    }
}

int main()
{
    test();
    printf ( "\n" );
    return 0;
}
